package leetcode.D700.T679;

/**
 * @Author: 18362
 * @Create: 2022-09-19 10:54:22 星期一
 */
class Solution {

    private boolean valid;

    public boolean judgePoint24(int[] cards) {
        double[] newCards = new double[4];
        for (int i = 0; i < 4; i++)
            newCards[i] = cards[i] * 1.0;
        dfs(newCards, new boolean[4], 0);
        return valid;
    }

    private void dfs(double[] cards, boolean[] visited, int used) {
        if (valid)
            return;
        if (used == 3) {
            double res = 0;
            for (int i = 0; i < 4; i++) {
                if (!visited[i]) {
                    res = cards[i];
                    break;
                }
            }
            if (Math.abs(res - 24) <= 0.001)
                valid = true;
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (visited[i])
                continue;
            for (int j = 0; j < 4; j++) {
                if (visited[j] || i == j)
                    continue;
                visited[j] = true;
                double a = cards[i], b = cards[j];
                cards[i] = a + b;
                dfs(cards, visited, used+1);
                cards[i] = a - b;
                dfs(cards, visited, used+1);
                cards[i] = a * b;
                dfs(cards, visited, used+1);
                if (b != 0) {
                    cards[i] = a / b;
                    dfs(cards, visited, used+1);
                }
                cards[i] = a;
                visited[j] = false;
            }
        }
    }
}